home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 10 - 1994 / 10.03 Mar 94 / Programmers' Challenge / ConnectTheDots.c next >
Encoding:
C/C++ Source or Header  |  1995-07-29  |  3.9 KB  |  165 lines  |  [TEXT/KAHL]
  1. /* ConnectTheDots -----------------------------------------
  2.  *
  3.  * Response to Jan 94 MacTech Programmer's Challenge.
  4.  *
  5.  * Object:
  6.  * Go around QD to draw color lines as fast as possible.
  7.  *
  8.  * Specs:
  9.  * nDots >= 2,
  10.  * handle only cases {(pixelSize,cmpSize,cmpCount) =
  11.  *    (8,8,1), (16,5,3), (32,8,3)},
  12.  * arbitrary alpha-bits,
  13.  * don't bother clipping,
  14.  * penSize = 1,1,
  15.  * patCopy mode.
  16.  *
  17.  * Notes on method:
  18.  * Specify segment by two endpoints {(x,y)=(a,b),(A,B)}.
  19.  * Form of line is {(x,y): (y-b)/(x-a) = m}, where slope 
  20.  * m = (B-b)/(A-a).  Then, y = m*(x-a)+b.
  21.  *
  22.  * Two successive values of y are:
  23.  * y2 = m*(x2-a)+b; y1 = m*(x1-a)+b, and the diff is,
  24.  * y2-y1 = m, since x2-x1 will always = 1 (pixel).
  25.  *
  26.  * Therefore, as we move from x to x, we add or sub
  27.  * m to the previous value of y.
  28.  *
  29.  * Speed:
  30.  * The cases that arise for combinations of {dy,dx}
  31.  * fall generally into 8 octants that cover the plane.
  32.  * Diagonally opposite octants are treated together,
  33.  * so there are 4 main cases to worry about. We first
  34.  * weed out 3 special cases: exactly horizontal,
  35.  * vertical, and diagonal segs. These are the simplest,
  36.  * most common, and fastest.
  37.  *
  38.  * In a given octant, one of |dx|, |dy| is strictly
  39.  * larger than the other. Our loop over pixels will
  40.  * always be over the larger magnitude for higher
  41.  * resolution drawing. The slope is formed then by
  42.  * smallNum/largeNum which must have quotient == 0,
  43.  * and remainder == smallNum. Adding the slope is
  44.  * a matter of accumulating remainders. If this sum
  45.  * exceeds largeNum, we move to next pixel.
  46.  *
  47.  * billKarsh
  48.  */
  49.  
  50. #pragma options( honor_register, !assign_registers )
  51. #pragma options( !check_ptrs )
  52.  
  53. #include    "ConnectTheDots.h"
  54.  
  55. #define        HiFiveMask    0xF800
  56. #define        Abs( a )    (a > 0 ? a : -a)
  57.  
  58. /* RGB2Index ----------------------------------------------
  59.  *
  60.  * Expects rgb color is an exact member of table, to
  61.  * avoid time spent close matching. Index is just
  62.  * position in table.
  63.  */
  64. static Byte RGB2Index(
  65.     ColorSpec    *cSpec,
  66.     RGBColor    *rgb )
  67. {
  68.     register ColorSpec    *cs = cSpec;
  69.     register short        entries = ((short*)cs)[-1]+1;
  70.     register short        red = rgb->red,
  71.                         green = rgb->green,
  72.                         blue = rgb->blue;
  73.     
  74.     do {
  75.         if( red   == cs->rgb.red  &&
  76.             blue  == cs->rgb.blue &&
  77.             green == cs->rgb.green )
  78.             return cs-cSpec;
  79.             
  80.         ++cs;
  81.     } while( --entries );
  82. }
  83.  
  84. /* Lines8 -------------------------------------------------
  85.  *
  86.  * Depth == 8 case.
  87.  *
  88.  * To maximize register usage, chose to put rowBytes
  89.  * in address reg.  Also, some vars like v_Cnt are
  90.  * dual purpose.
  91.  */
  92. static void Lines8(
  93.     PixMapPtr        pm,
  94.     Point            dot[],
  95.     unsigned short    nDots,
  96.     register Byte    pixel )
  97. {
  98.     register Ptr    at;
  99.     #include        "ConnectTheDots.com"
  100. }
  101.  
  102. /* Lines16 ------------------------------------------------
  103.  */
  104. static void Lines16(
  105.     PixMapPtr        pm,
  106.     Point            dot[],
  107.     unsigned short    nDots,
  108.     register short    pixel )
  109. {
  110.     register short    *at;
  111.     #include        "ConnectTheDots.com"
  112. }
  113.  
  114. /* Lines32 ------------------------------------------------
  115.  *
  116.  * align ensures 4-byte stack alignment for better speed.
  117.  */
  118. static void Lines32(
  119.     PixMapPtr        pm,
  120.     Point            dot[],
  121.     unsigned short    nDots,
  122.     short            align,
  123.     register long    pixel )
  124. {
  125.     register long    *at;
  126.     #include        "ConnectTheDots.com"
  127. }
  128.  
  129. /* ConnectTheDots -----------------------------------------
  130.  */
  131. void ConnectTheDots(
  132.     unsigned short    nDots,
  133.     Point            dot[],
  134.     PixMapHandle    pmH,
  135.     RGBColor        color )
  136. {
  137.     register PixMapPtr        pm = *pmH;
  138.     register unsigned short    pix16;
  139.     register Ptr            p32;
  140.     long                    pix32;
  141.     
  142.     if( pm->pixelSize == 8 ) {
  143.     
  144.         Lines8( pm, dot, nDots,
  145.             RGB2Index(&(**pm->pmTable).ctTable, &color) );
  146.     }
  147.     if( pm->pixelSize == 16 ) {
  148.  
  149.         pix16  = (color.red   & HiFiveMask) >> 1;
  150.         pix16 |= (color.green & HiFiveMask) >> 6;
  151.         pix16 |= (color.blue  & HiFiveMask) >> 11;
  152.         
  153.         Lines16( pm, dot, nDots, pix16 );
  154.     }
  155.     if( pm->pixelSize == 32 ) {
  156.     
  157.         p32 = ((Byte*)&pix32) + 1;
  158.         *p32++ = *(Byte*)&color.red;
  159.         *p32++ = *(Byte*)&color.green;
  160.         *p32++ = *(Byte*)&color.blue;
  161.         
  162.         Lines32( pm, dot, nDots, 0, pix32 );
  163.     }
  164. }
  165.